# 

# 

# ### 分支定界法（Branch and Bound）详解与Python代码示例

# 

# #### 分支定界法概述

# 

# 分支定界法（Branch and Bound, 简称B&B）是一种求解整数规划问题的有效算法。它结合了搜索与迭代的思想，通过系统地枚举候选解来寻找最优解。在求解过程中，算法将问题的可行解空间视为一个树形结构，其中根节点代表整个解空间，而树的分支则代表解空间的子集。算法通过不断地探索这些分支，并利用上界和下界的信息来剪枝，从而缩小搜索空间，提高求解效率。

# 

# #### 分支定界法的主要步骤

# 

# 1. **初始化**：设定目标函数的初始值为一个极大值（对于最小化问题）或极小值（对于最大化问题）。

# 2. **构造解空间树**：从根节点开始，根据问题的约束条件生成子节点。每个子节点代表一个可能的解或解的子集。

# 3. **优先选择节点**：选择一个节点进行扩展。通常，我们会选择那些具有较小上界或较大下界的节点进行扩展，以期望更快地找到最优解。

# 4. **剪枝**：在扩展节点时，如果某个分支的上界已经超过当前已知的最优解，或者该分支的下界已经小于当前已知的最优解（对于最小化问题），则可以剪去该分支及其所有子节点，因为它们不可能包含更优的解。

# 5. **更新目标函数**：如果当前节点是一个可行解，并且其目标函数值优于当前已知的最优解，则更新最优解。

# 6. **继续搜索**：重复步骤3至5，直到搜索完整个解空间或找到最优解为止。

# 

# #### Python代码示例

# 

# 下面是一个使用分支定界法求解0-1背包问题的Python代码示例。假设我们有n个物品，每个物品有一定的重量和价值，背包的总容量有限。我们需要选择若干物品放入背包，使得背包内物品的总价值最大，同时不超过背包的总容量。

# 

# 

import heapq



def knapsack_01(weights, values, capacity):

    n = len(weights)

    # 初始化最优解和当前解

    best_value = 0

    current_value = 0

    # 构造解空间树，使用最小堆来存储待扩展的节点

    heap = [(0, 0, 0)]  # (当前价值, 当前重量, 已选择的物品索引)

    

    while heap:

        current_value, current_weight, index = heapq.heappop(heap)

        

        # 如果当前解优于已知最优解，则更新最优解

        if current_value > best_value:

            best_value = current_value

        

        # 如果当前重量已经超过背包容量，则剪枝

        if current_weight > capacity:

            continue

        

        # 如果已经选择了所有物品，则比较当前解与最优解

        if index == n:

            if current_value > best_value:

                best_value = current_value

            continue

        

        # 选择不放入当前物品，继续搜索

        heapq.heappush(heap, (current_value, current_weight, index + 1))

        

        # 选择放入当前物品，并继续搜索

        if current_weight + weights[index] <= capacity:

            heapq.heappush(heap, (current_value + values[index], current_weight + weights[index], index + 1))

    

    return best_value



# 示例数据

weights = [10, 20, 30]

values = [60, 100, 120]

capacity = 50



# 调用函数求解

result = knapsack_01(weights, values, capacity)

print(f"最优解的价值为：{result}")
